#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void backtrack(vector<int> &selected_elements, vector<int> &candidates, vector<vector<int>> &result)
{
    // 当已选择的元素数量等于可供选择的元素数量时，将当前组合加入结果集
    if (selected_elements.size() == candidates.size())
    {
        result.push_back(selected_elements);
        return;
    }
    // 遍历可供选择的元素集合
    for (int i = 0; i < candidates.size(); ++i)
    {
        // 跳过重复元素，以确保结果中的每个元素只出现一次
        if (i > 0 && candidates[i] == candidates[i - 1])
        {
            continue;
        }
        // 将当前元素加入到已选择的元素集合中
        selected_elements.push_back(candidates[i]);
        // 创建一个临时集合，从中删除当前元素，以便在下一轮回溯中使用
        vector<int> temp = candidates;
        temp.erase(temp.begin() + i);
        // 递归调用回溯函数，继续寻找下一个元素
        backtrack(selected_elements, temp, result);
        // 回溯：移除最后一个添加的元素，探索其他可能的路径
        selected_elements.pop_back();
    }
}

vector<vector<int>> permuteUnique(vector<int> &nums)
{
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    vector<int> selected_elements;
    backtrack(selected_elements, nums, result);
    return result;
}

int main()
{
    // 生成测试数据
    vector<int> nums = {6, 7, 2, 3, 1, 3};

    // 输出原始数组
    cout << "Original array: ";
    for (auto num : nums)
    {
        cout << num << " ";
    }
    cout << endl;

    // 求解不重复排列
    vector<vector<int>> result = permuteUnique(nums);

    // 输出所有不重复排列
    cout << "Permutations with unique elements:" << endl;
    for (vector<int> &permutation : result)
    {
        for (int num : permutation)
        {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}


class Solution {
    vector<int> color;

public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        color.assign(n, -1);
        for (int i = 0; i < n; i++) {
            if (color[i] == -1 && !dfs(graph, i, 0))
                return false;
        }
        return true;
    }

    bool dfs(vector<vector<int>>& graph, int pos, int cl) {
        if (color[pos] != -1) {
            return color[pos] == cl;
        }

        color[pos] = cl;

        for (int node : graph[pos])
            if (!dfs(graph, node, !cl))
                return false;

        return true;
    }
};